# 方法一
# class Solution(object):
#     def boxDelivering(self, boxes, portsCount, maxBoxes, maxWeight):
#         n = len(boxes)
#         DP = [-1] * (n + 1)
#         DP[0] = 0
#         for i in range(n + 1):
#             if DP[i] >= 0 and i < n:
#                 val = boxes[i][1]
#                 last_port = boxes[i][0]
#                 duandian_j = i
#                 type = 1
#                 count = 1
#                 j = i + 1
#                 while j < n:
#                     if count + 1 <= maxBoxes and val + boxes[j][1] <= maxWeight:
#                         count += 1
#                         val += boxes[j][1]
#                         if boxes[j][0] != last_port:
#                             last_port = boxes[j][0]
#                             duandian_j = j - 1
#                             type += 1
#                         j += 1
#                     else:
#                         break
#                 if DP[j] == -1:
#                     DP[j] = DP[i] + type + 1
#                 else:
#                     DP[j] = min(DP[j], DP[i] + type + 1)
#                 if type > 1:
#                     if DP[duandian_j + 1] == -1:
#                         DP[duandian_j + 1] = DP[i] + type
#                     else:
#                         DP[duandian_j + 1] = min(DP[i] + type, DP[duandian_j + 1])
#         return DP[-1]

# 方法二
import collections


class Solution(object):
    def boxDelivering(self, boxes, portsCount, maxBoxes, maxWeight):
        n = len(boxes)
        g = [0] * n
        prefix = [0] * n
        prefix[0] = boxes[0][1]
        for i in range(1, n):
            prefix[i] = prefix[i - 1] + boxes[i][1]
            g[i] += g[i - 1] + int(boxes[i][0] != boxes[i - 1][0])
        st = collections.deque()
        st.append([0, -1])
        f = [float('inf')] * n
        for i in range(n):
            while st:
                _, index = st[0]
                if i - index > maxBoxes:
                    st.popleft()
                else:
                    if index == -1:
                        val = prefix[i]
                    else:
                        val = prefix[i] - prefix[index]
                    if val > maxWeight:
                        st.popleft()
                    else:
                        break
            f[i] = st[0][0] + g[i] + 2
            if i < n - 1:
                now_val = f[i] - g[i + 1]
                while st and st[-1][0] >= now_val:
                    st.pop()
                st.append([now_val, i])
        return f[-1]


data = Solution()
boxes = [[1,1],[2,1],[1,1]]
portsCount = 2
maxBoxes = 3
maxWeight = 3
print(data.boxDelivering(boxes, portsCount, maxBoxes, maxWeight))
boxes = [[1, 2], [3, 3], [3, 1], [3, 1], [2, 4]]
portsCount = 3
maxBoxes = 3
maxWeight = 6
print(data.boxDelivering(boxes, portsCount, maxBoxes, maxWeight))
boxes = [[1, 4], [1, 2], [2, 1], [2, 1], [3, 2], [3, 4]]
portsCount = 3
maxBoxes = 6
maxWeight = 7
print(data.boxDelivering(boxes, portsCount, maxBoxes, maxWeight))
boxes = [[2,4],[2,5],[3,1],[3,2],[3,7],[3,1],[4,4],[1,3],[5,2]]
portsCount = 5
maxBoxes = 5
maxWeight = 7
print(data.boxDelivering(boxes, portsCount, maxBoxes, maxWeight))